import java.util.*;

/**
 * @program: leetcode084
 * @author: JCM
 * @create: 2023-03-09 19:15
 * @description:
 **/
public class Main {
    // 穷举法,在 leetcode 上会超时
    public int largestRectangleArea1(int[] heights) {
        int len = heights.length;
        int res = 0;
        for(int i = 0; i < len; i++) {
            int left = i;
            int curH = heights[i];
            // 找左边最后一个高度大于等于当前柱子的柱子
            while(left > 0 && heights[left-1] >= curH) {
                left--;
            }
            // 找右边最后一个高度大于等于当前柱子的柱子
            int right = i;
            while(right < len-1 && heights[right+1] >= curH) {
                right++;
            }
            int width = right-left+1;
            res = Math.max(res,curH*width);

        }
        return res;
    }


    // 单调栈法，简单而言就是以 i 为高，分别找到左边第一个低于 height[i] 的下标和右边 第一个低于 height[i] 的下标
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for(int i = 0; i < n; i++) {
            while(!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        mono_stack.clear();
        for(int i = n-1; i >= 0; i--) {
            while(!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = Math.max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }

}
